package com.wj.algorithm.lintcode;

public class P116 {
    /*
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] a) {
        // write your code here
        if(a == null || a.length <= 0) {
            return false;
        }
        int len = a.length;
        if(len == 1) {//长度为1，不用判断，已经在终点
            return true;
        }

        int currentMinStepNeeded = 1;
        int currentSteps = 0;
        for (int stepIndex = len - 2; stepIndex >= 0; stepIndex --) {
            currentSteps = a[stepIndex];
            if(currentSteps >= currentMinStepNeeded) {
                //当前节点可以到达下一步
                currentMinStepNeeded = 1;
                continue;
            } else {
                //当前节点无法到达下一步，可以继续往前，但是要求下一个遍历节点的最小步长加一
                currentMinStepNeeded ++;
            }
        }
        if(currentSteps >= currentMinStepNeeded) {
            return true;
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        int[] a = {
//                5,8,3,0,6,7,9,6,3,4,5,2,0,6,2,6,7,10,8,0
//                2,3,1,1,4
//                4,3,4,10,0,7,5,5,1,0,5,7,7,9,6,7,3,10,8,2
                0
        };
        System.out.println(new P116().canJump(a));
    }
}
